package LeetCode.interview;

import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;

import LeetCode.interview._104_Maximum_Depth_of_Binary_Tree.TreeNode;
import sun.launcher.resources.launcher;
import sun.tools.jar.resources.jar;
import util.LogUtils;
import 算法.排序.归并排序.MergeSortTest1;
import 算法.排序.快速排序.QuickSort;

/*
 * 
原题　
	3Sum
	
	Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.
	
	Note:
	
	Elements in a triplet (a,b,c) must be in non-descending order. (ie, a ≤ b ≤ c)
	The solution set must not contain duplicate triplets.
	 
	
	    For example, given array S = {-1 0 1 2 -1 -4},
	
	    A solution set is:
	    (-1, 0, 1)
	    (-1, -1, 2)

题目大意
 
	找出三个数相加等于0，找到则合成一个一维数组，加入二维数组的结果中，
		要求：结果的二维数组中不能出现重复的一维数组
		
解题思路

		先升序排序，然后用第一重for循环确定第一个数字。
	
	然后在第二重循环里，第二、第三个数字分别从两端往中间扫。
	
	如果三个数的sum等于0，得到一组解。
	
	如果三个数的sum小于0，说明需要增大，所以第二个数往右移。
	
	如果三个数的sum大于0，说明需要减小，所以第三个数往左移。
	
	时间复杂度：O(n2)
	
	注意：
	
	1、排序之后天然满足non-descending order的要求
	
	2、为了避免重复，在没有空间要求情况下可以用map，但是也可以跳过重复元素来做。
	
 * @Date 2017-09-17 00：38
 */
public class _018_4Sum {
    public List<List<Integer>> threeSum(int[] nums) {
    	List<List<Integer>> rs = new ArrayList<List<Integer>>();
    	if (nums==null || nums.length<3)	return rs;
    	/**
    	 * 排序：
    	 * 	目的：排序后 再加上下方遍历时会跳过相同元素(eg:73行跳过相同第一位), 可以保证每次元素值都不同
    	 */
    	Arrays.sort(nums);
    	int N = nums.length;
    	int i = 0, j, k;
    	for (i = 0; i < N; i ++) {
    		 //skip same i
            while(i > 0 && i < N && nums[i] == nums[i-1])
                i ++;
    		j = i + 1;
    		k = N - 1;
    		//跳过重复
    		while (j < k) {
    			int sum = nums[i] + nums[j] + nums[k];
    			if (sum == 0) {
    				List<Integer> curLayout = new ArrayList<Integer>();
    				curLayout.add(nums[i]);
    				curLayout.add(nums[j]);
    				curLayout.add(nums[k]);
    				rs.add(curLayout);
    				j ++;
    				k --;
                    //skip same j
                    while(j < k && nums[j] == nums[j-1])
                        j ++;
                    //skip same k
                    while(k > j && nums[k] == nums[k+1])
                        k --;
    			} else if (sum < 0) {
    				j ++; 
    			    //skip same j
                    while(j < k && nums[j] == nums[j-1])
                        j ++;
    			} else {
    				k --;							//因为 下面有nums[k+1]为防止越界要先-1
                    //skip same k
                    while(k > j && nums[k] == nums[k+1])
                        k --;
    			}
    			
    		}
    	}
    	return rs;
    }
    
 
    
    public static void main(String[] args) {
		_018_4Sum obj = new _018_4Sum();
//		obj.twoSum(new int[]{1, 2, 3, 4, 5, 6, 7}, 7);
//		obj.twoSum2(new int[]{2, 7, 11, 15}, 9);
		LogUtils.println("结果", obj.threeSum(new int[]{-1, 0, 1, 2, -1, -4}));

	}

}
